using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sudoku.GamePlay
{
	public class Solver
	{
		#region CellValues
		private class CellValues
		{
			List<byte> Values;
			
			public CellValues()
			{
				RestoreValues();
			}

			public void RestoreValues()
			{
				Values = new List<byte>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
			}

			public void SetValues(List<byte> values)
			{
				Values.Clear();
				foreach (byte b in values)
				{
					Values.Add(b);
				}
			}

			public void RemoveValue(byte value)
			{
				Values.Remove(value);
			}

			public int PossibleValuesCount()
			{
				return Values.Count;
			}

			public List<byte> ValuesGet()
			{
				return Values;
			}

			public bool ValueFound()
			{
				return Values.Count == 1;
			}

			public byte ValueAt(int Position)
			{
				return Values.ElementAt(Position);
			}
		}
		#endregion

		CellValues[,] gridPossibleValues = new CellValues[9,9];
		int CRMEcount = 0;
		int LRSubCount = 0;
		int LRRowCount = 0;
		int LRColCount = 0;
		int TwinsSubCount = 0;
		int TwinsRowCount = 0;
		int TwinsColCount = 0;

		public Solver()
		{
			RestoreGridPossibleValuesList();
		}

		private void RestoreGridPossibleValuesList()
		{
			gridPossibleValues = new CellValues[9, 9]; 
			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					gridPossibleValues[i, j] = new CellValues();
				}
			}
		}

		public int SolveGrid(BoardCell[,] FatherGrid)
		{
			RestoreGridPossibleValuesList();

			//clone my grid..
			BoardCell[,] grid = new BoardCell[9, 9];
			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					grid[i,j] = new BoardCell(FatherGrid[i,j].Value);
				}
			}

			//debug!
			CRMEcount = 0;
			LRSubCount = 0;
			LRRowCount = 0;
			LRColCount = 0;
			TwinsSubCount = 0;
			TwinsRowCount = 0;
			TwinsColCount = 0;

			bool changed = true;
			while (changed)
			{
				SolverCRME(ref grid);
				changed = false;
				if (!IsGridSolved(ref grid))
				{
					changed = SolverLoneRangerSubSquare(ref grid);
					if (!IsGridSolved(ref grid))
					{
						if (!changed)
						{
							changed = SolverLoneRangerRow(ref grid);
							if (!IsGridSolved(ref grid))
							{
								if (!changed)
								{
									changed = SolverLoneRangerCol(ref grid);
									if (!IsGridSolved(ref grid))
									{
										if (!changed)
										{
											changed = SolverTwinsSubSquare(ref grid);
											if (!IsGridSolved(ref grid))
											{
												if (!changed)
												{
													changed = SolverTwinsRow(ref grid);
													if (!IsGridSolved(ref grid))
													{
														if (!changed)
														{
															changed = SolverTwinsCol(ref grid);
															if (!IsGridSolved(ref grid))
															{

															}
														}
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}

			int difficulty = (!IsGridSolved(ref grid)) ? 0 : CRMEcount + (LRSubCount * 2) + (LRRowCount * 2) + (LRColCount * 2) + (TwinsSubCount * 3) + (TwinsRowCount * 3) + (TwinsColCount * 3);
			System.Diagnostics.Debug.WriteLine("TotalCheck! CRME:" + CRMEcount 
												+ "\n LRSub:" + LRSubCount + " LRRow:" + LRRowCount + " LRCol:" + LRColCount
												+ "\n TSub:" + TwinsSubCount + " TRow:" + TwinsRowCount + " TCol:" + TwinsColCount + "");
			System.Diagnostics.Debug.WriteLine("Diff:" + difficulty + "\n");
			return difficulty;
		}

		private bool IsGridSolved(ref BoardCell[,] grid)
		{
			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					if (grid[i, j].Value == 0)
					{
						return false;
					}
				}
			}

			return true;
		}

		#region CRME
		private void SolverCRME(ref BoardCell[,] grid)
		{
			bool NewValueFound = true;
			int i, j;
			
			while (NewValueFound)
			{
				NewValueFound = false;
				i = j = 0;
				for (i = 0; i < 9; ++i)
				{
					for (j = 0; j < 9; ++j)
					{
						if (grid[i, j].Value == 0)
						{
							SolverCRME_CheckRow(ref grid, i, ref gridPossibleValues[i,j]);
							SolverCRME_CheckCol(ref grid, j, ref gridPossibleValues[i, j]);
							SolverCRME_CheckSubSquare(ref grid, i, j, ref gridPossibleValues[i, j]);

							if (gridPossibleValues[i, j].ValueFound())
							{
								grid[i, j].Value = gridPossibleValues[i, j].ValueAt(0);
								CRMEcount++;
								NewValueFound = true;
							}
						}
					}
				}
			}
		}

		private void SolverCRME_CheckRow(ref BoardCell[,] grid, int Row, ref CellValues cell)
		{
			for (int i = 0; i < 9; ++i)
			{
				if (grid[Row,i].Value != 0)
				{
					cell.RemoveValue(grid[Row, i].Value);
				}
			}
		}

		private void SolverCRME_CheckCol(ref BoardCell[,] grid, int Col, ref CellValues cell)
		{
			for (int i = 0; i < 9; ++i)
			{
				if (grid[i,Col].Value != 0)
				{
					cell.RemoveValue(grid[i, Col].Value);
				}
			}
		}

		private void SolverCRME_CheckSubSquare(ref BoardCell[,] grid, int Row, int Col, ref CellValues cell)
		{
			int FirstRow = (Row / 3) * 3;
			int LastRow = FirstRow + 3;

			int FirstCol = (Col / 3) * 3;
			int LastCol = FirstCol + 3;
			
			for (int i = FirstRow; i < LastRow; ++i)
			{
				for (int j = FirstCol; j < LastCol; ++j)
				{
					if (grid[i,j].Value != 0)
					{
						cell.RemoveValue(grid[i, j].Value);
					}
				}
			}
		}
		#endregion

		#region LoneRangers

		#region Lone Rangers SubSquares
		
		private bool SolverLoneRangerSubSquare(ref BoardCell[,] grid)
		{
			bool NewValueFound = false;
			
			for (int Row = 0; Row < 3; ++Row)
			{
				for (int Col = 0; Col < 3; ++Col)
				{
					int FirstRow = (Row / 3) * 3;
					int LastRow = FirstRow + 3;

					int FirstCol = (Col / 3) * 3;
					int LastCol = FirstCol + 3;
					for (int i = FirstRow; i < LastRow; ++i)
					{
						for (int j = FirstCol; j < LastCol; ++j)
						{
							if (grid[i, j].Value == 0)
							{
								bool found = LoneRangerSubSquareCheck(ref grid, FirstRow, FirstCol, LastRow, LastCol, i, j);
								if (found)
								{
									LRSubCount++;
									NewValueFound = true;
								}
							}
						}
					}
				}
			}

			return NewValueFound;
		}

		private bool LoneRangerSubSquareCheck(ref BoardCell[,] grid, 
												int FirstRow, 
												int FirstCol, 
												int LastRow, 
												int LastCol, 
												int CheckRow,
												int CheckCol)
		{
			CellValues ValuesCopy = new CellValues();
			ValuesCopy.SetValues(gridPossibleValues[CheckRow, CheckCol].ValuesGet()); 
			
			for (int i = FirstRow; i < LastRow; ++i)
			{
				for (int j = FirstCol; j < LastCol; ++j)
				{
					if (CheckRow != i || CheckCol != j)
					{
						if (grid[i, j].Value == 0)
						{
							for (int h = 0; h < gridPossibleValues[i, j].PossibleValuesCount(); ++h)
							{
								ValuesCopy.RemoveValue(gridPossibleValues[i, j].ValueAt(h));
							}
						}
					}
				}
			}

			if (ValuesCopy.ValueFound())
			{
				gridPossibleValues[CheckRow, CheckCol] = ValuesCopy;
				grid[CheckRow, CheckCol].Value = gridPossibleValues[CheckRow, CheckCol].ValueAt(0);
				return true;
			}

			return false;
		}

		#endregion

		#region Lone Rangers Row

		private bool SolverLoneRangerRow(ref BoardCell[,] grid)
		{
			bool NewValueFound = false;
			
			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					if (grid[i, j].Value == 0)
					{
						bool found = LoneRangerRowCheck(ref grid, i, j);
						if (found)
						{
							LRRowCount++;
							NewValueFound = true;
						}
					}
				}
			}

			return NewValueFound;
		}

		private bool LoneRangerRowCheck(ref BoardCell[,] grid, int CheckRow, int CheckCol)
		{
			CellValues ValuesCopy = new CellValues();
			ValuesCopy.SetValues(gridPossibleValues[CheckRow, CheckCol].ValuesGet()); 
			
			for (int j = 0; j < 9; ++j)
			{
				if (CheckCol != j)
				{
					if (grid[CheckRow, j].Value == 0)
					{
						for (int h = 0; h < gridPossibleValues[CheckRow, j].PossibleValuesCount(); ++h)
						{
							ValuesCopy.RemoveValue(gridPossibleValues[CheckRow, j].ValueAt(h));
						}
					}
				}
			}

			if (ValuesCopy.ValueFound())
			{
				gridPossibleValues[CheckRow, CheckCol] = ValuesCopy;
				grid[CheckRow, CheckCol].Value = gridPossibleValues[CheckRow, CheckCol].ValueAt(0);
				return true;
			}

			return false;
		}

		#endregion

		#region Lone Rangers Col

		private bool SolverLoneRangerCol(ref BoardCell[,] grid)
		{
			bool NewValueFound = false;

			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					if (grid[i, j].Value == 0)
					{
						bool found = LoneRangerColCheck(ref grid, i, j);
						if (found)
						{
							LRColCount++;
							NewValueFound = true;
						}
					}
				}
			}

			return NewValueFound;
		}

		private bool LoneRangerColCheck(ref BoardCell[,] grid, int CheckRow, int CheckCol)
		{
			CellValues ValuesCopy = new CellValues();
			ValuesCopy.SetValues(gridPossibleValues[CheckRow, CheckCol].ValuesGet());

			for (int i = 0; i < 9; ++i)
			{
				if (CheckRow != i)
				{
					if (grid[i, CheckCol].Value == 0)
					{
						for (int h = 0; h < gridPossibleValues[i, CheckCol].PossibleValuesCount(); ++h)
						{
							ValuesCopy.RemoveValue(gridPossibleValues[i, CheckCol].ValueAt(h));
						}
					}
				}
			}

			if (ValuesCopy.ValueFound())
			{
				gridPossibleValues[CheckRow, CheckCol] = ValuesCopy;
				grid[CheckRow, CheckCol].Value = gridPossibleValues[CheckRow, CheckCol].ValueAt(0);
				return true;
			}

			return false;
		}

		#endregion

		#endregion

		#region Twins

		#region Twins SubSquares

		private bool SolverTwinsSubSquare(ref BoardCell[,] grid)
		{
			bool NewValueFound = false;

			for (int Row = 0; Row < 3; ++Row)
			{
				for (int Col = 0; Col < 3; ++Col)
				{
					int FirstRow = (Row / 3) * 3;
					int LastRow = FirstRow + 3;

					int FirstCol = (Col / 3) * 3;
					int LastCol = FirstCol + 3;
					for (int i = FirstRow; i < LastRow; ++i)
					{
						for (int j = FirstCol; j < LastCol; ++j)
						{
							if (grid[i, j].Value == 0 && gridPossibleValues[i, j].PossibleValuesCount() == 2)
							{
								//found a pair
								if (TwinsSubSquareCheck(ref grid, FirstRow, FirstCol, LastRow, LastCol, i, j))
								{
									NewValueFound = true;
								}
							}
						}
					}
				}
			}

			return NewValueFound;
		}

		private bool TwinsSubSquareCheck(ref BoardCell[,] grid, 
											int FirstRow, int FirstCol, 
											int LastRow, int LastCol, 
											int CheckRow, int CheckCol)
		{
			bool newValueFound = false;
			for (int i = FirstRow; i < LastRow; ++i)
			{
				for (int j = FirstCol; j < LastCol; ++j)
				{
					if (CheckRow != i || CheckCol != j)
					{
						if (grid[i, j].Value == 0 && gridPossibleValues[i, j].PossibleValuesCount() == 2)
						{
							bool twinsFound = true;
							for (int h = 0; h < 2; ++h)
							{
								if (gridPossibleValues[i, j].ValueAt(h) != gridPossibleValues[i, j].ValueAt(h))
									twinsFound = false;
							}

							if (twinsFound)
							{
								if (TwinsSubSquareRemove(ref grid, FirstRow, FirstCol, LastRow, LastCol, ref gridPossibleValues[i, j]))
								{
									newValueFound = true;
								}

								return newValueFound;
							}
						}
					}
				}
			}

			return newValueFound;
		}

		private bool TwinsSubSquareRemove(ref BoardCell[,] grid, 
											int FirstRow, int FirstCol, 
											int LastRow, int LastCol,
											ref CellValues Twin)
		{
			bool newValueFound = false;
			for (int i = FirstRow; i < LastRow; ++i)
			{
				for (int j = FirstCol; j < LastCol; ++j)
				{
					if (grid[i, j].Value == 0 && gridPossibleValues[i, j].PossibleValuesCount() > 2)
					{
						for (int h = 0; h < Twin.PossibleValuesCount(); ++h)
						{
							gridPossibleValues[i, j].RemoveValue(Twin.ValueAt(h)); 
						}

						if (gridPossibleValues[i, j].ValueFound())
						{
							grid[i, j].Value = gridPossibleValues[i, j].ValueAt(0);
							TwinsSubCount++;
							newValueFound = true;
						}
					}
				}
			}

			return newValueFound;
		}

		#endregion

		#region Twins Row

		private bool SolverTwinsRow(ref BoardCell[,] grid)
		{
			bool NewValueFound = false;

			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					if (grid[i, j].Value == 0 && gridPossibleValues[i, j].PossibleValuesCount() == 2)
					{
						//found a pair
						if (TwinsRowCheck(ref grid, i, j))
						{
							NewValueFound = true;
						}	
					}
				}
			}

			return NewValueFound;
		}

		private bool TwinsRowCheck(ref BoardCell[,] grid, int CheckRow, int CheckCol)
		{
			bool newValueFound = false;
			
			for (int j = 0; j < 9; ++j)
			{
				if (CheckCol != j)
				{
					if (grid[CheckRow, j].Value == 0)
					{
						if (grid[CheckRow, j].Value == 0 && gridPossibleValues[CheckRow, j].PossibleValuesCount() == 2)
						{
							bool twinsFound = true;
							for (int h = 0; h < 2; ++h)
							{
								if (gridPossibleValues[CheckRow, j].ValueAt(h) != gridPossibleValues[CheckRow, j].ValueAt(h))
									twinsFound = false;
							}

							if (twinsFound)
							{
								if (TwinsRowRemove(ref grid, CheckRow, ref gridPossibleValues[CheckRow, j]))
								{
									newValueFound = true;
								}

								return newValueFound;
							}
						}
					}
				}
			}

			return newValueFound;
		}

		private bool TwinsRowRemove(ref BoardCell[,] grid, int Row, ref CellValues Twin)
		{
			bool newValueFound = false;

			for (int j = 0; j < 9; ++j)
			{
				if (grid[Row, j].Value == 0 && gridPossibleValues[Row, j].PossibleValuesCount() > 2)
				{
					for (int h = 0; h < Twin.PossibleValuesCount(); ++h)
					{
						gridPossibleValues[Row, j].RemoveValue(Twin.ValueAt(h));
					}

					if (gridPossibleValues[Row, j].ValueFound())
					{
						grid[Row, j].Value = gridPossibleValues[Row, j].ValueAt(0);
						TwinsRowCount++;
						newValueFound = true;
					}
				}
			}

			return newValueFound;
		}

		#endregion

		#region Twins Col

		private bool SolverTwinsCol(ref BoardCell[,] grid)
		{
			bool NewValueFound = false;

			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					if (grid[i, j].Value == 0 && gridPossibleValues[i, j].PossibleValuesCount() == 2)
					{
						//found a pair
						if (TwinsColCheck(ref grid, i, j))
						{
							NewValueFound = true;
						}
					}
				}
			}

			return NewValueFound;
		}

		private bool TwinsColCheck(ref BoardCell[,] grid, int CheckRow, int CheckCol)
		{
			bool newValueFound = false;

			for (int i = 0; i < 9; ++i)
			{
				if (CheckRow != i)
				{
					if (grid[i, CheckCol].Value == 0)
					{
						if (grid[i, CheckCol].Value == 0 && gridPossibleValues[i, CheckCol].PossibleValuesCount() == 2)
						{
							bool twinsFound = true;
							for (int h = 0; h < 2; ++h)
							{
								if (gridPossibleValues[i, CheckCol].ValueAt(h) != gridPossibleValues[i, CheckCol].ValueAt(h))
									twinsFound = false;
							}

							if (twinsFound)
							{
								if (TwinsColRemove(ref grid, CheckCol, ref gridPossibleValues[i, CheckCol]))
								{
									newValueFound = true;
								}

								return newValueFound;
							}
						}
					}
				}
			}

			return newValueFound;
		}

		private bool TwinsColRemove(ref BoardCell[,] grid, int Col, ref CellValues Twin)
		{
			bool newValueFound = false;

			for (int i = 0; i < 9; ++i)
			{
				if (grid[i, Col].Value == 0 && gridPossibleValues[i, Col].PossibleValuesCount() > 2)
				{
					for (int h = 0; h < Twin.PossibleValuesCount(); ++h)
					{
						gridPossibleValues[i, Col].RemoveValue(Twin.ValueAt(h));
					}

					if (gridPossibleValues[i, Col].ValueFound())
					{
						grid[i, Col].Value = gridPossibleValues[i, Col].ValueAt(0);
						TwinsColCount++;
						newValueFound = true;
					}
				}
			}

			return newValueFound;
		}

		#endregion

		#endregion

	}
}
